package com.gorkr;


import java.sql.Array;
import java.util.*;


/**
 * 寻找重复子树
 */
public class L652 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    class Solution {
        public ArrayList<TreeNode> res= new ArrayList<>();
        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {

            HashMap<String, Integer> map = new HashMap<>();
            return null;
        }

        public String traverse(TreeNode root, HashMap<String, Integer> map){
            if(root==null){
                return "#";
            }

            // 后序遍历
            String subString =  traverse(root.left,map) + "," + traverse(root.right,map) + "," + root.val;

            int freq = map.getOrDefault(subString, 0);
            if(freq==1){
                res.add(root);
            }
            map.put(subString,freq+1);
            return subString;
     }
    }

}
